In recent years, use of mobile communications devices for voice telephone services, email or text messaging services and even multi-media services has become commonplace, among mobile professionals and throughout the more general consumer population. Mobile communication services provided through public cellular or PCS (personal communication service) type networks, particularly for voice telephone service, have become virtually ubiquitous across much of the world. The mobile communication services offered by a wireless carrier or operator of a mobile communication network may include different messaging services that enable different mobile subscribers to exchange various types of messages with one another via an application or interface executable at their respective mobile devices. Some of these subscribers may need to exchange messages including sensitive or confidential information and thus, may require a secure way to exchange such messages over a mobile communication network. For example, enterprise subscribers (e.g., commercial entities, government agencies, healthcare organizations, financial institutions, etc.) or other individual subscribers (e.g., doctors or stock traders) may need a secure way to send and receive such messages between different mobile devices of users (e.g., messages between different enterprise personnel or messages to and from clients). However, conventional mobile-to-mobile messaging solutions relating to the transmission of messages over a radio link or through a wireless communication network generally require a compromise between security, ease-of-use and limitations with respect to the type of device or service that may be used.